
/**
 * A class representing a node in the quad tree.
 **/
abstract class QuadTreeNode
{
    /**
     * Value used to determine the x-axis size of the image
     **/
    static int gcmp = 4194304;
    /**
     * Value used to determine the y-axis size of the image
     **/
    static int lcmp = 1048576;

    /**
     * The quadrant that this node represents (i.e., northwest, northeast,
     * southwest, or southeast).
     **/
    protected Quadrant quadrant;
    /**
     * Node that represents the northwest quadrant of the image
     **/
    protected QuadTreeNode nw;
    /**
     * Node that represents the northeast quadrant of the image
     **/
    protected QuadTreeNode ne;
    /**
     * Node that represents the southwest quadrant of the image
     **/
    protected QuadTreeNode sw;
    /**
     * Node that represents the southeast quadrant of the image
     **/
    protected QuadTreeNode se;
    /**
     * Node that represents the parent quadrant of the image
     **/
    protected QuadTreeNode parent;

    // enumeration for direction
    public final static int NORTH = 0;
    public final static int EAST = 1;
    public final static int SOUTH = 2;
    public final static int WEST = 3;

    /**
     * Create a leaf node in the Quad Tree.
     *
     * @param childType if there's a parent, the type of child this node represents
     * @param parent the parent quad tree node
     **/
    QuadTreeNode(Quadrant quad, QuadTreeNode parent)
    {
        this(quad, null, null, null, null, parent);
    }

    /**
     * Create a node in the quad tree.
     *
     * @param childType if there's a parent, the type of child
     * @param nw the node represent the northwest quadrant
     * @param ne the node represent the northeast quadrant
     * @param sw the node represent the southwest quadrant
     * @param se the node represent the southeast quadrant
     **/
    private QuadTreeNode(Quadrant quad, QuadTreeNode nw, QuadTreeNode ne,
                         QuadTreeNode sw, QuadTreeNode se, QuadTreeNode parent)
    {
        this.quadrant = quad;
        this.nw = nw;
        this.ne = ne;
        this.sw = sw;
        this.se = se;
        this.parent = parent;
    }

    /**
     * Set the children of the quad tree node.
     *
     * @param nw the node represent the northwest quadrant
     * @param ne the node represent the northeast quadrant
     * @param sw the node represent the southwest quadrant
     * @param se the node represent the southeast quadrant
     **/
    protected void setChildren(QuadTreeNode nw, QuadTreeNode ne,
                               QuadTreeNode sw, QuadTreeNode se)
    {
        this.nw = nw;
        this.ne = ne;
        this.sw = sw;
        this.se = se;
    }

    /**
     * Return the node representing the north west quadrant.
     * @return the node representing the north west quadrant.
     **/
    final QuadTreeNode getNorthWest() { return nw; }
    /**
     * Return the node representing the north east quadrant.
     * @return the node representing the north east quadrant.
     **/
    final QuadTreeNode getNorthEast() { return ne; }
    /**
     * Return the node representing the south west quadrant.
     * @return the node representing the south west quadrant.
     **/
    final QuadTreeNode getSouthWest() { return sw; }
    /**
     * Return the node representing the south east quadrant.
     * @return the node representing the south east quadrant.
     **/
    final QuadTreeNode getSouthEast() { return se; }

    /**
     * Create an image which is represented using a QuadTreeNode.
     * @param size size of image
     * @param center_x x coordinate of center
     * @param center_y; y coordinate of center
     * @param parent parent quad tree node
     * @param quadrant the quadrant that the sub tree is in
     * @param level the level of the tree
     **/
    static QuadTreeNode createTree(int size, int center_x, int center_y,
                                   QuadTreeNode parent, Quadrant quadrant, int level)
    {
        QuadTreeNode node;

        int intersect = checkIntersect(center_x, center_y, size);
        size = size/2;
        if (intersect == 0 && size < 512) {
            node = new WhiteNode(quadrant, parent);
        } else if (intersect == 2) {
            node = new BlackNode(quadrant, parent);
        } else {
            if (level == 0) {
                node = new BlackNode(quadrant, parent);
            } else {
                node = new GreyNode(quadrant, parent);
                QuadTreeNode sw = createTree(size, center_x-size, center_y-size,
                                             node, Quadrant.cSouthWest, level - 1);
                QuadTreeNode se = createTree(size, center_x+size, center_y-size,
                                             node, Quadrant.cSouthEast, level - 1);
                QuadTreeNode ne = createTree(size, center_x+size, center_y+size,
                                             node, Quadrant.cNorthEast, level - 1);
                QuadTreeNode nw = createTree(size, center_x-size, center_y+size,
                                             node, Quadrant.cNorthWest, level - 1);
                node.setChildren(nw, ne, sw, se);
            }
        }
        return node;
    }

    /**
     * Compute the total perimeter of a binary image that is represented
     * as a quadtree using Samet's algorithm.
     *
     * @param size the size of the image that this node represents (size X size).
     * @return the size of the perimeter of the image.
     **/
    abstract public int perimeter(int size);

    /**
     * Sum the perimeter of all white leaves in the two specified
     * quadrants of the sub quad tree rooted at this node.
     *
     * @param quad1 the first specified quadrant
     * @param quad2 the second specified quadrant
     * @param size the size of the image represented by this node.
     * @return the perimeter of the adjacent nodes
     **/
    abstract public int sumAdjacent(Quadrant quad1, Quadrant quad2, int size);

    /**
     * Return the neighbor of this node in the given direction which is
     * greater than or equal in size to this node.  If the node doesn't
     * exist, then a grey node of equal size is returned.  Otherwise,
     * the node is adjacent to the border of the image and null is
     * returned.
     *
     * @param dir the direction of the neighbor
     * @return the appropriate neighbor based upon the direction, or null
     **/
    QuadTreeNode gtEqualAdjNeighbor(int dir)
    {
        QuadTreeNode q;
        if (parent != null && quadrant.adjacent(dir)) {
            q = parent.gtEqualAdjNeighbor(dir);
        } else {
            q = parent;
        }

        if (q != null && q instanceof GreyNode) {
            return quadrant.reflect(dir).child(q);
        } else {
            return q;
        }
    }

    /**
     * Count the number of leaves in the quad tree.
     * @return the number of leaves in the quad tree.
     **/
    int countTree()
    {
        if (nw == null && ne == null && sw == null && se == null) {
            return 1;
        } else {
            return sw.countTree() + se.countTree() + ne.countTree() +
                nw.countTree();
        }
    }

    private static int checkOutside(int x, int y)
    {
        int euclid = x*x+y*y;
        if (euclid > gcmp) return 1;
        if (euclid < lcmp) return -1;
        return 0;
    }

    private static int checkIntersect(int center_x, int center_y, int size)
    {
        if (checkOutside(center_x+size, center_y+size) == 0 &&
            checkOutside(center_x+size, center_y-size) == 0 &&
            checkOutside(center_x-size, center_y-size) == 0 &&
            checkOutside(center_x-size, center_y+size) == 0)
            return 2;

        int sum = checkOutside(center_x+size, center_y+size) +
            checkOutside(center_x+size, center_y-size) +
            checkOutside(center_x-size, center_y-size) +
            checkOutside(center_x-size, center_y+size);

        if ((sum==4) || (sum==-4)) return 0;

        return 1;
    }

    public String toString()
    {
        return getClass().getName() + " " + quadrant.getClass().getName();
    }
}
